Міністерство освіти і науки України
Національний Університет « Львівська Політехніка»
Кафедра ЕОМ
Звіт
до лабораторної роботи №5
на тему: « Структура даних „БІНАРНЕ ДЕРЕВО ПОШУКУ”.»
Варіант 9.
Виконав:
ст. гр. КІ-1
Львів-2007
Назва роботи: Структури даних “Бінарне дерево пошуку”.
Мета роботи: Закріпити теоретичні знання та оволодіти практичними навиками опрацювання структур даних “Бінарне дерево пошуку”. Засвоїти техніку створення та опрацювання складних типів даних.
Теоретична частина:
Деревом називається множина взаємно-зв’язаних елементів які називаються вузлами розташованих по рівнях. Бінарне дерево- це скінченна множина вузлів кожен з яких або порожній, або складається з кореня пов’язаного з двома різними бінарними деревами які називається лівим і правим піддеревом.
Виконання роботи
Завдання:
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Виконати обхід дерева у заданому порядку і підрахувати:
кількість вершин дерева, що обраховується при проходженні дерева у прямому порядку;
кількість листків дерева, що обраховується при проходженні дерева у зворотньому порядку;
кількість вузлів, які мають тільки одного нащадка, що обраховується при проходженні дерева у симетричному порядку.
Визначити, чи побудоване дерево є строго бінарним деревом.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct node
{
int data;
struct node *leftson, *rightson;
}*binary_tree;
void Init(binary_tree *root_ptr);
int Empty(binary_tree root);
binary_tree WhoRight(binary_tree tree_node);
void PutLeftLeft(binary_tree tree_node);
binary_tree Who(binary_tree root, int new_data);
void PutRight(binary_tree root, int new_data);
binary_tree Find(binary_tree root, int search_data);
int GoStraight(binary_tree root,int k,int z);
void GoSymmetric(binary_tree root);
void GoReverse(binary_tree root);
int Compare(binary_tree root1,binary_tree root2);
binary_tree WhoFather(binary_tree root, binary_tree knot);
binary_tree WhoBrother(binary_tree root, binary_tree knot);
void AddSearchTree(binary_tree *root_ptr, int new_data);
void DeleteSearchTree(binary_tree *root_ptr, int del_data);
void PrintLevel(binary_tree root, int k, int i);
void PrintTurningTree(binary_tree root, int h);
int kil=0;
int mas1[100],i=0;
void main()
{
int z,k=0,lustku,vyzlu;
double ser=0;
binary_tree t1,p ;
int x;
unsigned i,n;
Init(&t1);
printf("Enter the number of knots of binary tree 1: ");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&x);
AddSearchTree(&t1, x);
};
printf("\n");
kil=0;
k=GoStraight(t1,k,0); //kilkist vyzliv pru priamomy prohodgenni
printf("\nkilkist vyzliv=%d",kil);
printf("\n");
vyzlu=kil;
kil=0;
GoSymmetric(t1); //kilkist vyzliv z 1 nashcadkom pru symetru4nomy
z=kil;
printf("\nkilkist vyzliv z 1 nashcadkom=%d",z);
printf("\n");
kil=0; i=0;
GoReverse(t1); //kilkist lustkiv pru zvorotniomy
z=kil;
printf("\nkilkist lustkiv=%d",z);
printf("\n");
lustku=kil;
PrintLevel(t1,20,1);
printf("\n");
if(2*lustku-1==vyzlu)
puts("derevo stroho binarne");
else
puts("derevo ne stroho binarne");
getch();
return;
}
// ????????????? ??
void Init(binary_tree *root_ptr)
{
*root_ptr = NULL;
}
// ????????? ?? ?? ???????
int Empty(binary_tree root)
{
return root == NULL;
}
// ????? ?????? ???? ???????? ????? ??
binary_tree WhoLeft(binary_tree tree_node)
{
if (tree_node)
return tree_node->leftson;
else
return tree_node;
}
// ????? ??????? ???? ???????? ????? ??
binary_tree WhoRight(binary_tree tree_node)
{
if (tree_node)
return tree_node->rightson;
else
return tree_node;
}
// ????????? ?????? ????? ?? ?? ??????? ?????????
binary_tree MakeNode(int new_data)
{
binary_tree new_node;
new_node =(struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_nod...
